﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    public class _70ClimbingStairs:IRun
    {
        /*
         * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
         * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
         * 注意：给定 n 是一个正整数。
         * 
         * 示例 1：
         * 输入： 2
         * 输出： 2
         * 解释： 有两种方法可以爬到楼顶。
         * 1.  1 阶 + 1 阶
         * 2.  2 阶
         * 
         * 示例 2：
         * 输入： 3
         * 输出： 3
         * 解释： 有三种方法可以爬到楼顶。
         * 1.  1 阶 + 1 阶 + 1 阶
         * 2.  1 阶 + 2 阶
         * 3.  2 阶 + 1 阶
         * 
         */

        /* 
         * 解题思路：拆解
         * 1、当有N层楼梯时，爬到（N-1）有X种方法，爬到（N-2）有Y种方法；
         * 2、那么爬到N层的方法有（N-1） + （N-2）种；
         *      （N-1）层，只能选择1，到第N层；
         *      （N-2）层，只能选择2，到第N层；若选择一层一层上，该方法与（N-1）中重合；
         * 3、故，F（N）= F（N-1）+ F（N-2）；
         * 4、将其转换为：斐波那契数列问题；
         * 5、注意优化；
         */

        public void Run()
        {
            int i = ClimbStairs1(44,null);

            int i1 = ClimbStairs2(44);
        }
        public int ClimbStairs(int n)
        {
            if (n == 1)
                return 1;

            if (n == 2)
                return 2;

            if (n >= 3)
                return ClimbStairs(n - 1) + ClimbStairs(n - 2);
            return 0;
        }


        public int ClimbStairs1(int n , Dictionary<int, int> map)
        {
            Dictionary<int, int> _Result;
            if (map == null)
                map = new Dictionary<int, int>();
            _Result = map;

            if (n == 1)
                return 1;

            if (n == 2)
                return 2;

            if (n >= 3)
            {
                if (!_Result.ContainsKey(n - 1))
                    _Result.Add(n-1,ClimbStairs1(n-1,_Result));

                if (!_Result.ContainsKey(n - 2))
                    _Result.Add(n - 2, ClimbStairs1(n - 2, _Result));

                return _Result[n - 1] + _Result[n - 2];
            }
            return 0;
        }

        public int ClimbStairs2(int n)
        {
            if (n == 1)
                return 1;

            if (n == 2)
                return 2;


            int a = 1, b = 2, c = 0;
            for (int i = 3; i <= n; i++)
            {
                c = a + b;
                a = b;
                b = c;
            }

            return c;
        }
    }
}
